package aa;

public class AA1 {

    public static void main(String[] args) {
        
        // Define o tamanho da parede
        final int tamanhoParede = 1000000;//(int)(1 + (Math.random() * 100000));
        
        // Define a posicao da porta
        final int posicaoPorta = 0; //(int)(1 + (Math.random() * tamanhoParede))
        
        // Exibe onde a porte será posicionada
        System.out.println("Porta posicionada em: " + posicaoPorta);
        
        // Cria a parede
        final boolean[] parede = new boolean[tamanhoParede];
        
        // Adiciona a porta
        parede[posicaoPorta] = true;
        
        // Invoca o algoritmo para encontrar a porta
        final int portaEncontrada = encontrarPorta(parede);
        
        // Exibe o resultado
        System.out.println("Porta encontrada em: " + portaEncontrada);
        
    }
    
    private static int encontrarPorta(final boolean[] parede){
        
        int posicaoPorta = -1;
        
        // Define o centro da parede
        final int centro = (parede.length + 1) / 2;
        
        // Procura a porta
        for(int i = centro; i < parede.length && posicaoPorta == -1; i++){
            
            int j = centro;
            
            // Anda para direita
            for(; j <= i && posicaoPorta == -1; j++){
                if(parede[j]){
                    posicaoPorta = j;
                }
            }
            
            // Volta para o centro
            while(j != centro){
                j--;
            }
            
            // Anda para a esquerda
            for(; (centro - j - 1) <= (i - centro) && posicaoPorta == -1; j--){
                if(parede[j]){
                    posicaoPorta = j;
                }
            }
            
            // Volta para o centro
            while(j != centro){
                j++;
            }
            
            
        }
        
        return posicaoPorta;
        
    }
            
}
